{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Robot Room Cleaner"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #backtracking #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #回溯 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: cleanRoom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #扫地机器人"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>房间中的某个位置上有一个机器人，你需要控制它清扫房间。房间被建模为一个 <code>m x n</code> 的二进制网格，其中 <code>0</code> 表示单元格中有障碍物，<code>1</code> 表示空单元格。</p>\n",
    "\n",
    "<p>机器人从一个未知的空单元格开始出发，并且你无法访问网格，但你可以使用给定的 API <code>Robot</code> 控制机器人。</p>\n",
    "\n",
    "<p>你的任务是使用机器人清扫整个房间（即清理房间中的每个空单元格）。机器人具有四个给定的API，可以前进、向左转或向右转。每次转弯 90 度。</p>\n",
    "\n",
    "<p>当机器人试图移动到一个存在障碍物的单元格时，它的碰撞传感器会检测到障碍物，并停留在当前单元格。</p>\n",
    "\n",
    "<p>设计一个算法，使用下述 API 清扫整个房间：</p>\n",
    "\n",
    "<pre>\n",
    "interface Robot {\n",
    "&nbsp; // 若下一个单元格为空，则返回 true ，并移动至该单元格。\n",
    "&nbsp; // 若下一个单元格为障碍物，则返回 false ，并停留在当前单元格。\n",
    "&nbsp; boolean move();\n",
    "\n",
    "  // 在调用 turnLeft/turnRight 后机器人会停留在当前单元格。\n",
    "&nbsp; // 每次转弯 90 度。\n",
    "&nbsp; void turnLeft();\n",
    "&nbsp; void turnRight();\n",
    "\n",
    "  // 清理当前单元格。\n",
    "  void clean();\n",
    "}\n",
    "</pre>\n",
    "\n",
    "<p><strong>注意</strong> 扫地机器人的初始方向向上。你可以假定网格的四周都被墙包围。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>自定义测试：</strong></p>\n",
    "\n",
    "<p>输入只用于初始化房间和机器人的位置。你需要「盲解」这个问题。换而言之，你必须在对房间和机器人位置一无所知的情况下，只使用 4 个给出的 API 解决问题。&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/17/lc-grid.jpg\" style=\"width: 500px; height: 314px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3\n",
    "<strong>输出：</strong>Robot cleaned all rooms.\n",
    "<strong>解释：</strong>\n",
    "房间内的所有单元格用 0 或 1 填充。\n",
    "0 表示障碍物，1 表示可以通过。 \n",
    "机器人从 row=1, col=3 的初始位置出发。\n",
    "在左上角的一行以下，三列以右。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>room = [[1]], row = 0, col = 0\n",
    "<strong>输出：</strong>Robot cleaned all rooms.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == room.length</code></li>\n",
    "\t<li><code>n == room[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 200</code></li>\n",
    "\t<li><code>room[i][j]</code> 为 <code>0</code> 或 <code>1</code>.</li>\n",
    "\t<li><code>0 &lt;= row &lt;&nbsp;m</code></li>\n",
    "\t<li><code>0 &lt;= col &lt; n</code></li>\n",
    "\t<li><code>room[row][col] == 1</code></li>\n",
    "\t<li>所有空单元格都可以从起始位置出发访问到。</li>\n",
    "</ul>\n",
    "\n",
    "<ol>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [robot-room-cleaner](https://leetcode.cn/problems/robot-room-cleaner/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [robot-room-cleaner](https://leetcode.cn/problems/robot-room-cleaner/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]]\\n1\\n3', '[[1]]\\n0\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        cur = robot.room\n",
    "        for i in range(len(cur)):\n",
    "            for j in range(len(cur[0])):\n",
    "                if cur[i][j]:\n",
    "                    robot.row = i\n",
    "                    robot.col = j\n",
    "                    robot.clean()\n",
    "        # print(robot.row, robot.col)\n",
    "        # print(robot.dmap)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.robot = None\n",
    "        self.cleaned = set()\n",
    "        self.dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        self.robot = robot\n",
    "        self.backtrack(0, 0, 0)\n",
    "\n",
    "    def backtrack(self, i, j, d):\n",
    "        # use backtrack to keep path\n",
    "        self.robot.clean()\n",
    "        self.cleaned.add((i, j))\n",
    "        # keep robot facing up when start and finish?? or same dir\n",
    "        # assume when coming back, robot keep same dir when moving forward\n",
    "        # need to mark cleaned cell\n",
    "\n",
    "        # if (i + self.dirs[d][0], j + self.dirs[d][1]) not in self.cleaned and self.robot.move():\n",
    "        #     self.backtrack(i + self.dirs[d][0], j + self.dirs[d][1], d)    # next cell\n",
    "\n",
    "        # # try left cell\n",
    "        # d = (d + 3) % 4\n",
    "        # self.robot.turnLeft()\n",
    "        # if (i + self.dirs[d][0], j + self.dirs[d][1]) not in self.cleaned and self.robot.move():\n",
    "        #     self.backtrack(i + self.dirs[d][0], j + self.dirs[d][1], d)\n",
    "\n",
    "        # d = (d + 2) % 4\n",
    "        # # try right cell\n",
    "        # self.robot.turnRight()\n",
    "        # self.robot.turnRight()\n",
    "        # if (i + self.dirs[d][0], j + self.dirs[d][1]) not in self.cleaned and self.robot.move():\n",
    "        #     self.backtrack(i + self.dirs[d][0], j + self.dirs[d][1], d)\n",
    "        \n",
    "        # # returning, keep same dir\n",
    "        # self.robot.turnRight()\n",
    "        # self.robot.move()\n",
    "        # self.robot.turnRight()\n",
    "        # self.robot.turnRight()\n",
    "\n",
    "        # return\n",
    "\n",
    "        # Try all directions\n",
    "        for _ in range(4):\n",
    "            ni, nj = i + self.dirs[d][0], j + self.dirs[d][1]\n",
    "            if (ni, nj) not in self.cleaned and self.robot.move():\n",
    "                # If can move and not cleaned, clean next cell\n",
    "                self.backtrack(ni, nj, d)\n",
    "                # Return to the current position and direction\n",
    "                self.robot.turnLeft()\n",
    "                self.robot.turnLeft()\n",
    "                self.robot.move()\n",
    "                self.robot.turnLeft()\n",
    "                self.robot.turnLeft()\n",
    "            # Try the next direction\n",
    "            self.robot.turnRight()\n",
    "            d = (d + 1) % 4\n",
    "        return\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        self.dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        self.visited = set()\n",
    "        self.robot = robot\n",
    "        self.DFS(0, 0, 0)\n",
    "    \n",
    "    def DFS(self, offsetX, offsetY, curDir):\n",
    "        self.robot.clean()\n",
    "        self.visited.add((offsetX, offsetY))\n",
    "\n",
    "        for idx in range(4):\n",
    "            newDir = (idx + curDir) % 4\n",
    "            dirX, dirY = self.dirs[newDir]\n",
    "            newX = offsetX + dirX\n",
    "            newY = offsetY + dirY\n",
    "            \n",
    "            if (newX, newY) not in self.visited and self.robot.move():\n",
    "                self.DFS(newX, newY, newDir)\n",
    "                # step-back\n",
    "                self.robot.turnRight()\n",
    "                self.robot.turnRight()\n",
    "                self.robot.move()\n",
    "                self.robot.turnRight()\n",
    "                self.robot.turnRight()\n",
    "            \n",
    "            self.robot.turnRight()\n",
    "\n",
    "\n",
    "'''\n",
    "DFS(offsetX, offsetY, dir)\n",
    "\n",
    "'''\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.robot = None\n",
    "        self.cleaned = set()    # record cleaned\n",
    "        self.dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]  # up, right, down, left\n",
    "\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        self.robot = robot\n",
    "        self.backtrack(0, 0, 0) # starting position as (0, 0) with d pointing up\n",
    "\n",
    "    def backtrack(self, i, j, d) -> None:\n",
    "        self.robot.clean()\n",
    "        self.cleaned.add((i, j))\n",
    "\n",
    "        # from (i, j), explore 4 dirs to clean next cell\n",
    "        for _ in range(4):\n",
    "            di, dj = self.dirs[d]\n",
    "            ni, nj = i + di, j + dj\n",
    "            if (ni, nj) not in self.cleaned and self.robot.move():    # robot moved to (ni, nj)\n",
    "                self.backtrack(ni, nj, d)   # robot status (ni, nj, d)\n",
    "                # reset robot status d when coming back from (ni, nj) to (i, j)\n",
    "                self.comeback()\n",
    "\n",
    "            d = (d + 1) % 4\n",
    "            self.robot.turnRight()\n",
    "\n",
    "        return\n",
    "\n",
    "    def comeback(self) -> None:\n",
    "        self.robot.turnRight()\n",
    "        self.robot.turnRight()\n",
    "        self.robot.move()\n",
    "        self.robot.turnRight()\n",
    "        self.robot.turnRight()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        #backtract\n",
    "        dx = [0,1,0,-1]\n",
    "        dy = [-1,0,1,0]\n",
    "        visited = set()\n",
    "        def dfs(i,j,cur_dir):\n",
    "            robot.clean()\n",
    "            visited.add((i,j))\n",
    "            for k in range(4):\n",
    "                next_dir = cur_dir\n",
    "                x = i+dx[next_dir]\n",
    "                y = j+dy[next_dir]\n",
    "                if((x,y) not in visited and robot.move()):\n",
    "                    dfs(x,y,next_dir)\n",
    "                    robot.turnRight()\n",
    "                    robot.turnRight()\n",
    "                    robot.move()\n",
    "                    robot.turnRight()\n",
    "                    robot.turnRight()\n",
    "                robot.turnRight()\n",
    "                cur_dir = (1+cur_dir)%4\n",
    "        dfs(0,0,0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        # class variable就像c++里的类静态数据\n",
    "        directions=[(-1,0),(0,1),(1,0),(0,-1)]\n",
    "        visited = set()\n",
    "        def go_back()->None:\n",
    "          robot.turnRight()\n",
    "          robot.turnRight()\n",
    "          robot.move()\n",
    "          robot.turnRight()\n",
    "          robot.turnRight()\n",
    "\n",
    "        def backtrack(cell:tuple=(0,0),face:int=0)->None:\n",
    "          visited.add(cell)\n",
    "          robot.clean()\n",
    "      # try to clean four directions in a close wise way\n",
    "          for i in range(4):\n",
    "            n_face=(face+i)%4\n",
    "            n_cell=(cell[0]+directions[n_face][0],cell[1]+directions[n_face][1])\n",
    "        # The cell in front of current cell could be cleaned\n",
    "            if n_cell not in visited and robot.move():\n",
    "              backtrack(n_cell,n_face)\n",
    "              go_back()\n",
    "        # The cell in front of current cell is cleaned or could not be cleaned\n",
    "            robot.turnRight()\n",
    "      \n",
    "        backtrack((0,0),0)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        visited = set()\n",
    "        def back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        \n",
    "        def backtrack(i = 0, j = 0, d = 0):\n",
    "            visited.add((i, j))\n",
    "            robot.clean()\n",
    "            for k in range(4):\n",
    "                curDir = (d + k) % 4\n",
    "                x = i + directions[curDir][0]\n",
    "                y = j + directions[curDir][1]\n",
    "                if (x, y) not in visited and robot.move():\n",
    "                    backtrack(x, y, curDir)\n",
    "                    back()\n",
    "                robot.turnRight()\n",
    "        \n",
    "        backtrack()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def dfs(i, j, dx, dy):\n",
    "            robot.clean()\n",
    "            for _ in range(4):\n",
    "\n",
    "                x, y = i + dx, j + dy\n",
    "                # 调用move函数 如果成功 就到了x,y位置 此时直接打扫\n",
    "                if (x, y) not in vis and robot.move():\n",
    "                    vis.add((x, y))\n",
    "                    dfs(x, y, dx, dy)\n",
    "                    # 要从x y位置回到i j位置的话 就需要两下右转然后往下走一步\n",
    "                    robot.turnRight()\n",
    "                    robot.turnRight()\n",
    "                    robot.move()\n",
    "                    # 再两下左转回到原来的方向 即可完美恢复到当时的现场状况\n",
    "                    robot.turnLeft()\n",
    "                    robot.turnLeft()\n",
    "                # 调换方向 然后两个坐标的变化幅度就会产生这样的变化\n",
    "                dx, dy = dy, -dx\n",
    "                robot.turnRight()\n",
    "        vis = {(0, 0)}\n",
    "\n",
    "        # 一开始向上 方向就是(-1, 0)\n",
    "        dfs(0, 0, -1, 0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        dirs = [-1, 0, 1, 0, -1]\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(x, y, d):\n",
    "            print(x,y,d)\n",
    "            robot.clean()\n",
    "            visited.add((x, y))\n",
    "            for i in range(4):\n",
    "                cur = (i + d) % 4\n",
    "                nxt_x, nxt_y = x + dirs[cur], y + dirs[cur+1]\n",
    "                if (nxt_x, nxt_y) not in visited and robot.move():\n",
    "                    dfs(nxt_x, nxt_y, cur)\n",
    "                    # 这里要回溯一下, 因为判断条件里有一个 move(), 我们要让它退回原来的位置\n",
    "                    robot.turnRight()\n",
    "                    robot.turnRight()\n",
    "                    robot.move()\n",
    "                    robot.turnLeft()\n",
    "                    robot.turnLeft()\n",
    "                robot.turnRight()\n",
    "        \n",
    "        dfs(robot.row, robot.col, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        \n",
    "        def backtrack(cell = (0, 0), d = 0):\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "            # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "            for i in range(4):\n",
    "                new_d = (d + i) % 4\n",
    "                new_cell = (cell[0] + directions[new_d][0], \\\n",
    "                    cell[1] + directions[new_d][1])\n",
    "            \n",
    "                if not new_cell in visited and robot.move():\n",
    "                    backtrack(new_cell, new_d)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "        # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        visited = set()\n",
    "        backtrack()\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:       \n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            \n",
    "        def backtrack(cell = (0, 0), d = 0):\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "            # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "            for i in range(4):\n",
    "                new_d = (d + i) % 4\n",
    "                new_cell = (cell[0] + directions[new_d][0], \\\n",
    "                            cell[1] + directions[new_d][1])\n",
    "                \n",
    "                if not new_cell in visited and robot.move():\n",
    "                    backtrack(new_cell, new_d)\n",
    "                    go_back()\n",
    "                # turn the robot following chosen direction : clockwise\n",
    "                robot.turnRight()\n",
    "    \n",
    "        # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        visited = set()\n",
    "        backtrack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution(object):       \n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            \n",
    "        def backtrack(cell = (0, 0), d = 0):\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "            # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "            for i in range(4):\n",
    "                new_d = (d + i) % 4\n",
    "                new_cell = (cell[0] + directions[new_d][0], \\\n",
    "                            cell[1] + directions[new_d][1])\n",
    "                \n",
    "                if not new_cell in visited and robot.move():\n",
    "                    backtrack(new_cell, new_d)\n",
    "                    go_back()\n",
    "                # turn the robot following chosen direction : clockwise\n",
    "                robot.turnRight()\n",
    "    \n",
    "        # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        visited = set()\n",
    "        backtrack()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        def dfs(x,y,direct):\n",
    "            if (x,y) in pos:\n",
    "                return\n",
    "            pos.add((x,y))\n",
    "            robot.clean()\n",
    "            for i in range(4):\n",
    "                if robot.move():    # 0->1 0<-1\n",
    "                    dfs(x+directions[(direct+i)%4][0],y+directions[(direct+i)%4][1],(direct+i)%4)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "        \n",
    "        directions = ((-1,0),(0,1),(1,0),(0,-1))\n",
    "        pos = set()\n",
    "        dfs(0,0,0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        def backtrack(cell=(0, 0), d=0):\n",
    "\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "\n",
    "            for i in range(4):\n",
    "                new_d = (d + i) % 4\n",
    "                new_cell = (cell[0] + directions[new_d][0], cell[1] + directions[new_d][1])\n",
    "\n",
    "                if not new_cell in visited and robot.move():\n",
    "                    backtrack(new_cell, new_d)\n",
    "                    go_back()\n",
    "\n",
    "                robot.turnRight()\n",
    "\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "\n",
    "        visited = set()\n",
    "        backtrack()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.robot = None\n",
    "        self.visited = set()\n",
    "        self.dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        self.robot = robot\n",
    "        self.backtrack(0, 0, 0)\n",
    "        return\n",
    "\n",
    "    def backtrack(self, i: int, j: int, d: int) -> None:\n",
    "        self.robot.clean()\n",
    "        self.visited.add((i, j))\n",
    "\n",
    "        for _ in range(4):  # find next cell based on current direction\n",
    "            di, dj = self.dirs[d]\n",
    "            ni, nj = i + di, j + dj\n",
    "            if (ni, nj) not in self.visited and self.robot.move():\n",
    "                # note robot already goes to next cell!\n",
    "                self.backtrack(ni, nj, d)\n",
    "                # coming back robot still in ni, nj, d, need to reset these states to i, j, d\n",
    "                self.comeback()\n",
    "            d = (d + 1) % 4\n",
    "            self.robot.turnRight()\n",
    "        return\n",
    "\n",
    "    def comeback(self) -> None:\n",
    "        self.robot.turnRight()\n",
    "        self.robot.turnRight()\n",
    "        self.robot.move()\n",
    "        self.robot.turnRight()\n",
    "        self.robot.turnRight()             \n",
    "        return   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        visited = set()\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        def backtrack(cell, dir):\n",
    "            robot.clean()\n",
    "            visited.add(cell)\n",
    "            directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "            for i in range(4):\n",
    "                d = directions[(dir+i) % 4]\n",
    "                new_cell = (cell[0] + d[0], cell[1] + d[1])\n",
    "                if new_cell not in visited and robot.move():\n",
    "                    backtrack(new_cell, (dir+i) % 4)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "        backtrack((0,0), 0)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        seen = set((0,0))\n",
    "        directions = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        def traverse(x,y,d):\n",
    "            robot.clean()\n",
    "            for i in range(4):\n",
    "                new_d = (d+i)%4\n",
    "                new_x = x+directions[new_d][0]\n",
    "                new_y = y+directions[new_d][1]\n",
    "                if (new_x, new_y) not in seen and robot.move():\n",
    "                    seen.add((new_x, new_y))\n",
    "                    traverse(new_x,new_y,new_d)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "\n",
    "        traverse(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "up, right, down, left = 0, 1, 2, 3\n",
    "turn = [0, 3, 2, 1]\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def dfs(p, d, visited):\n",
    "            nonlocal robot\n",
    "            visited.add(p)\n",
    "            p_robot = (p[0]+1, p[1]+3)\n",
    "            robot.clean()\n",
    "            i, j = p\n",
    "            for k in range(4):\n",
    "                nd = (d+k)%4\n",
    "                posDiff = directions[nd]\n",
    "                np = (i+posDiff[0], j+posDiff[1])\n",
    "                np_robot = (np[0]+1, np[1]+3)\n",
    "                if np not in visited and robot.move():\n",
    "                    dfs(np, nd, visited)\n",
    "                    robot.turnRight()\n",
    "                    robot.turnRight()\n",
    "                    robot.move()\n",
    "                    robot.turnRight()\n",
    "                    robot.turnRight()\n",
    "                robot.turnRight()\n",
    "        dfs((0, 0), up, set())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        direct = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        visited = set()\n",
    "\n",
    "        def go_back():\n",
    "\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        def backtrack(cell = (0, 0), d = 0):\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "\n",
    "            for i in range(4):\n",
    "                new_d = (d + i ) % 4\n",
    "                newcell = (cell[0] + direct[new_d][0], cell[1] + direct[new_d][1])\n",
    "                if newcell not in visited and robot.move():\n",
    "                    backtrack(newcell, new_d)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "\n",
    "        backtrack()\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        visited = set()\n",
    "        self.dfsHelper((0,0),visited,robot,0)\n",
    "    \n",
    "    def dfsHelper(self,po,visited,robot,direction):\n",
    "        print(direction)\n",
    "        visited.add(po)\n",
    "        robot.clean()\n",
    "        moves = [[-1,0],[0,1],[1,0],[0,-1]]\n",
    "\n",
    "        for d in range(4):\n",
    "            i = (direction+d) % 4\n",
    "            newPo = (po[0]+moves[i][0],po[1]+moves[i][1])\n",
    "        \n",
    "            if newPo not in visited and robot.move():\n",
    "                self.dfsHelper(newPo,visited,robot,i) \n",
    "                robot.turnRight()\n",
    "                robot.turnRight()\n",
    "                robot.move()\n",
    "                robot.turnRight()\n",
    "                robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        \n",
    "        def backtrack(cell = (0, 0), d = 0):\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "            # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "            for i in range(4):\n",
    "                new_d = (d + i) % 4\n",
    "                new_cell = (cell[0] + directions[new_d][0], \\\n",
    "                    cell[1] + directions[new_d][1])\n",
    "            \n",
    "                if not new_cell in visited and robot.move():\n",
    "                    backtrack(new_cell, new_d)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "        # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        visited = set()\n",
    "        backtrack()\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]\n",
    "        visited = set()\n",
    "\n",
    "        def goback():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        def dfs(cell, dir):\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "\n",
    "            for i in range(4):\n",
    "                new_dir = (i + dir) % 4\n",
    "                newCell = (cell[0]+directions[new_dir][0], cell[1]+directions[new_dir][1])\n",
    "\n",
    "                if newCell not in visited and robot.move():\n",
    "                    dfs(newCell, new_dir)\n",
    "                    goback()\n",
    "                robot.turnRight()\n",
    "\n",
    "        dfs((0,0), 0)\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        visited = set()\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        def go_back():\n",
    "\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        def backtrack(cell=(0, 0), d=0):\n",
    "\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "\n",
    "            for i in range(4):\n",
    "                new_d = (d + i) % 4\n",
    "                new_cell = (cell[0] + directions[new_d][0], cell[1] + directions[new_d][1])\n",
    "\n",
    "                if not new_cell in visited and robot.move():\n",
    "                    backtrack(new_cell, new_d)\n",
    "                    go_back()\n",
    "\n",
    "                robot.turnRight()\n",
    "\n",
    "        backtrack()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        visit = set()\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] # (-1, 0)\n",
    "        def dfs(index, i, j):\n",
    "            robot.clean()\n",
    "            visit.add((i, j))\n",
    "            for k in range(4):\n",
    "                dx, dy = directions[(index + k) % 4]\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if (x, y) not in visit and robot.move():\n",
    "                    dfs((index + k) % 4, x, y)\n",
    "                    go_back()\n",
    "\n",
    "                robot.turnRight()  \n",
    "                 \n",
    "        dfs(0, 0, 0)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        def dfs(coord, towards):\n",
    "            # print(coord)\n",
    "            if coord not in visited and robot.move():\n",
    "                visited.add(coord)\n",
    "                robot.clean()\n",
    "                for _ in range(4):\n",
    "                    next_coord = (coord[0]+directions[towards][0], coord[1]+directions[towards][1])\n",
    "                    # if next_coord not in visited:\n",
    "                    dfs(next_coord, towards)\n",
    "                    robot.turnRight()\n",
    "                    towards = (towards + 1) % 4\n",
    "                robot.turnRight()\n",
    "                robot.turnRight()\n",
    "                robot.move()\n",
    "                robot.turnRight()\n",
    "                robot.turnRight()\n",
    "        visited = set([(0, 0)])\n",
    "        robot.clean()\n",
    "        towards = 0\n",
    "        for _ in range(4):\n",
    "            next_coord = (0+directions[towards][0], 0+directions[towards][1])\n",
    "            # if next_coord not in visited:\n",
    "            dfs(next_coord, towards)\n",
    "            robot.turnRight()\n",
    "            towards = (towards + 1) % 4\n",
    "        # print(visited)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        visited = set()\n",
    "\n",
    "        def back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        def backtrack(x, y, d):        \n",
    "            robot.clean()\n",
    "            visited.add((x, y))\n",
    "            for i in range(4):\n",
    "                _d = (d + i) % 4\n",
    "                _x = x + directions[_d][0]\n",
    "                _y = y + directions[_d][1]\n",
    "\n",
    "                if (_x, _y) not in visited and robot.move():\n",
    "                    backtrack(_x, _y, _d)\n",
    "                    back()\n",
    "                robot.turnRight()\n",
    "\n",
    "        backtrack(0, 0, 0)   \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        visit = set()\n",
    "        # (1, 0) 代表facing up, (0, 1)代表facing right，(-1, 0)代表facing down, (0, -1)达标facing left \n",
    "        # 注意顺序不能变\n",
    "        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        # directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] #上右下左\n",
    "        def dfs(index, i, j):\n",
    "            robot.clean()\n",
    "            visit.add((i, j))\n",
    "            for k in range(4):\n",
    "                #下一个方向，顺时针\n",
    "                new_index = (index + k) % 4\n",
    "                dx, dy = directions[new_index]\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if (x, y) not in visit and robot.move():\n",
    "                    dfs(new_index, x, y)\n",
    "                    go_back() #后退，回溯\n",
    "                robot.turnRight() #顺时针，           \n",
    "        dfs(0, 0, 0)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            \n",
    "        def backtrack(cell = (0, 0), d = 0):\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "            # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "            for i in range(4):\n",
    "                new_d = (d + i) % 4\n",
    "                new_cell = (cell[0] + directions[new_d][0], \\\n",
    "                            cell[1] + directions[new_d][1])\n",
    "                \n",
    "                if not new_cell in visited and robot.move():\n",
    "                    backtrack(new_cell, new_d)\n",
    "                    go_back()\n",
    "                # turn the robot following chosen direction : clockwise\n",
    "                robot.turnRight()\n",
    "    \n",
    "        # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        visited = set()\n",
    "        backtrack()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        # room = robot.room\n",
    "        # m,n = len(room),len(room[0])\n",
    "        startX,startY = robot.row,robot.col\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        \n",
    "        dirs = [(-1,0),(0,1),(1,0),(0,-1)]\n",
    "        visit = set()\n",
    "        def dfs(r,c,d):\n",
    "            visit.add((r,c))\n",
    "            robot.clean()\n",
    "            for i in range(4):\n",
    "                x,y = dirs[(d + i) % 4]\n",
    "                nx,ny = x + r,y + c\n",
    "                if (nx,ny) not in visit and robot.move():\n",
    "                    dfs(nx,ny,(d + i)%4)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "        \n",
    "        return dfs(startX,startY,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        visit = set()\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] #上右下左\n",
    "        def dfs(index, i, j):\n",
    "            robot.clean()\n",
    "            visit.add((i, j))\n",
    "            for k in range(4):\n",
    "                #下一个方向，顺时针\n",
    "                new_index = (index + k) % 4\n",
    "                dx, dy = directions[new_index]\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if (x, y) not in visit and robot.move():\n",
    "                    dfs(new_index, x, y)\n",
    "                    go_back() #后退，回溯\n",
    "                robot.turnRight() #顺时针，           \n",
    "        dfs(0, 0, 0)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        visited = set()\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        def go_back():\n",
    "\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        def backtrack(cell=(0, 0), d=0):\n",
    "\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "\n",
    "            for i in range(4):\n",
    "                new_d = (d + i) % 4\n",
    "                # 相邻\n",
    "                new_cell = (cell[0] + directions[new_d][0], cell[1] + directions[new_d][1])\n",
    "                # 没访问过 且可以访问\n",
    "                if not new_cell in visited and robot.move():\n",
    "                    backtrack(new_cell, new_d)\n",
    "                    # 回溯\n",
    "                    go_back()\n",
    "                # 正常往右转\n",
    "                robot.turnRight()\n",
    "\n",
    "        backtrack()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        visited = set()\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        def back(robot):\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        def trackback(cell=(0, 0), d = 0):\n",
    "            visited.add(cell)\n",
    "            robot.clean()\n",
    "            for i in range(4):\n",
    "                nd = (d + i) % 4\n",
    "\n",
    "                newcell = (cell[0] + directions[nd][0], cell[1] + directions[nd][1])\n",
    "                if not newcell in visited and robot.move():\n",
    "                    # visited.add(newcell)\n",
    "                    trackback(newcell, nd)\n",
    "                    back(robot)\n",
    "                robot.turnRight()\n",
    "\n",
    "        trackback((0, 0), 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "\n",
    "        visit = set()\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        def dfs(index, i, j):\n",
    "            robot.clean()\n",
    "            visit.add((i, j))\n",
    "            for k in range(4):\n",
    "                new_index = (index + k) % 4\n",
    "                dx, dy = dirs[new_index]\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if (x, y) not in visit and robot.move():\n",
    "                    dfs(new_index, x, y)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "        dfs(0, 0, 0)\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()   # back i pos\n",
    "        visit = set()\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        def dfs(d, i, j):\n",
    "            robot.clean()\n",
    "            visit.add((i, j))\n",
    "            for k in range(4):\n",
    "                new_d = (d + k) % 4 # must new_d\n",
    "                dx, dy = dirs[new_d]\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if (x, y) not in visit and robot.move():\n",
    "                    dfs(new_d, x, y)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "        return dfs(0, 0, 0)\n",
    "\n",
    "     \n",
    " \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()   # back i pos\n",
    "        visit = set()\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        def dfs(d, i, j):\n",
    "            robot.clean()\n",
    "            visit.add((i, j))\n",
    "            for k in range(4):\n",
    "                new_d = (d + k) % 4 # must new_d since after robot.turnright, d will be used again to create new_d\n",
    "                dx, dy = dirs[new_d]\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if (x, y) not in visit and robot.move():\n",
    "                    dfs(new_d, x, y)\n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "        return dfs(0, 0, 0)\n",
    "\n",
    "     \n",
    " \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        directions = [(-1,0), (0,1), (1,0), (0,-1)]\n",
    "        visited = set()\n",
    "        def back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        \n",
    "        def helper(i=0, j=0, d=0):\n",
    "            # print(i, j)\n",
    "            if (i, j) in visited:\n",
    "                return\n",
    "            print(i, j)\n",
    "            robot.clean()\n",
    "            visited.add((i, j))\n",
    "            for k in range(4):\n",
    "                newD = (d+k) % 4\n",
    "                x = i + directions[newD][0]\n",
    "                y = j + directions[newD][1]\n",
    "                if robot.move():\n",
    "                    helper(x, y, newD)\n",
    "                    back()\n",
    "                robot.turnRight()\n",
    "\n",
    "        helper()\n",
    "\n",
    "\n",
    "#   [1,1,2,2,2,0,1,1],\n",
    "#   [1,1,2,2,2,0,1,1],\n",
    "#   [1,0,2,2,2,1,1,1],\n",
    "#   [0,0,0,1,0,0,0,0],\n",
    "#   [1,1,1,1,1,1,1,1]\n",
    "\n",
    "\n",
    "#   [1,1,2,2,2,0,1,1],\n",
    "#   [1,2,2,2,2,0,1,1],\n",
    "#   [1,0,2,2,2,1,1,1],\n",
    "#   [0,0,0,2,0,0,0,0],\n",
    "#   [2,2,2,2,2,2,2,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        visit = set()\n",
    "        # (1, 0) 代表facing up, (0, 1)代表facing right，(-1, 0)代表facing down, (0, -1)达标facing left \n",
    "        # 注意顺序不能变\n",
    "        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        def dfs(index, i, j):\n",
    "            robot.clean()\n",
    "            visit.add((i, j))\n",
    "            for k in range(4):\n",
    "                #下一个方向，顺时针\n",
    "                new_index = (index + k) % 4\n",
    "                dx, dy = directions[new_index]\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if (x, y) not in visit and robot.move():\n",
    "                    dfs(new_index, x, y)\n",
    "                    go_back() #后退，回溯\n",
    "                robot.turnRight() #顺时针，           \n",
    "        dfs(0, 0, 0)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        direction = [(-1, 0), (0, - 1), (1, 0), (0, 1)]\n",
    "        visit = set()\n",
    "        def dfs(i, j, d):\n",
    "            robot.clean()\n",
    "            for idx in range(4):\n",
    "                nd = (d + idx) % 4 \n",
    "                x = i + direction[nd][0]\n",
    "                y = j + direction[nd][1]\n",
    "                if (x, y) not in visit and robot.move():\n",
    "                    visit.add((x, y))\n",
    "                    dfs(x, y, nd)\n",
    "                    robot.turnLeft()\n",
    "                    robot.turnLeft()\n",
    "                    robot.move()\n",
    "                    robot.turnLeft()\n",
    "                    robot.turnLeft()\n",
    "                robot.turnLeft()\n",
    "        dfs(0, 0, 0)\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        def back():\n",
    "            robot.turnLeft()\n",
    "            robot.turnLeft()\n",
    "            robot.move()\n",
    "            robot.turnLeft()\n",
    "            robot.turnLeft()\n",
    "\n",
    "        def dfs(x, y, direction):\n",
    "            robot.clean()\n",
    "            visited.add((x, y))\n",
    "            for i in range(4):\n",
    "                next_direction = (direction + i) % 4\n",
    "                dx, dy = directions[next_direction][0], directions[next_direction][1]\n",
    "                next_x, next_y = x + dx, y + dy\n",
    "                if (next_x, next_y) not in visited and robot.move():\n",
    "                    dfs(next_x, next_y, next_direction)\n",
    "                    back()\n",
    "                robot.turnLeft()\n",
    "\n",
    "\n",
    "        visited = set()\n",
    "        directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]\n",
    "        dfs(0, 0, 0)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        directions = [(-1,0), (0,1), (1,0), (0,-1)]\n",
    "        visited = set()\n",
    "        def back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "        \n",
    "        def helper(i=0, j=0, d=0):\n",
    "            # print(i, j)\n",
    "            # if (i, j) in visited:\n",
    "            #     return\n",
    "            print(i, j)\n",
    "            robot.clean()\n",
    "            visited.add((i, j))\n",
    "            for k in range(4):\n",
    "                newD = (d+k) % 4\n",
    "                x = i + directions[newD][0]\n",
    "                y = j + directions[newD][1]\n",
    "                if (x,y) not in visited and robot.move():\n",
    "                    helper(x, y, newD)\n",
    "                    back()\n",
    "                robot.turnRight()\n",
    "\n",
    "        helper()\n",
    "\n",
    "\n",
    "#   [1,1,2,2,2,0,1,1],\n",
    "#   [1,1,2,2,2,0,1,1],\n",
    "#   [1,0,2,2,2,1,1,1],\n",
    "#   [0,0,0,1,0,0,0,0],\n",
    "#   [1,1,1,1,1,1,1,1]\n",
    "\n",
    "\n",
    "#   [1,1,2,2,2,0,1,1],\n",
    "#   [1,2,2,2,2,0,1,1],\n",
    "#   [1,0,2,2,2,1,1,1],\n",
    "#   [0,0,0,2,0,0,0,0],\n",
    "#   [2,2,2,2,2,2,2,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the robot's control interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class Robot:\n",
    "#    def move(self):\n",
    "#        \"\"\"\n",
    "#        Returns true if the cell in front is open and robot moves into the cell.\n",
    "#        Returns false if the cell in front is blocked and robot stays in the current cell.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnLeft(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def turnRight(self):\n",
    "#        \"\"\"\n",
    "#        Robot will stay in the same cell after calling turnLeft/turnRight.\n",
    "#        Each turn will be 90 degrees.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def clean(self):\n",
    "#        \"\"\"\n",
    "#        Clean the current cell.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "\n",
    "        # 0,1,2,3, up,right,down,left\n",
    "        \n",
    "        def go_back():\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            robot.move()\n",
    "            robot.turnRight()\n",
    "            robot.turnRight()\n",
    "            return \n",
    "\n",
    "        visited = collections.defaultdict(int)\n",
    "        def DFS(x,y,d):\n",
    "            visited[(x,y)]=1\n",
    "            robot.clean()\n",
    "\n",
    "            \n",
    "            directs = [(x,y+1),(x+1,y),(x,y-1),(x-1,y)]\n",
    "            for i in range(4):\n",
    "                dx, dy = directs[(d+i)%4]\n",
    "                if visited[(dx,dy)]>0:\n",
    "                    robot.turnRight()\n",
    "                    continue \n",
    "                \n",
    "                if robot.move():\n",
    "                    DFS(dx,dy,(d+i)%4)\n",
    "                   \n",
    "                    go_back()\n",
    "                robot.turnRight()\n",
    "            #go_back()\n",
    "            return \n",
    "        \n",
    "        DFS(0,0,0)\n",
    "        return\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
